package BinaryTree.后序.review;

import 其他.DataStructure.TreeNode;
import org.junit.Test;

/*
157
 */
public class 公共祖先 {
    @Test
    public void test() {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t0 = new TreeNode(0);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);

        t3.left=t5;
        t3.right=t1;
        t5.left=t6;
        t5.right=t2;
        t2.left=t7;
        t2.right=t4;
        t1.left=t0;
        t1.right=t8;

//        TreeNode zuxian = lowestCommonAncestor(t3, t5, t4);
        // rot为祖先
        TreeNode zuxian = lowestCommonAncestor(t3, t5, t1);
        System.out.println(zuxian.val);

    }



    TreeNode t1,t2;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        t1=p;t2=q;
        back(root);
        return zuxian;
    }

    TreeNode zuxian;
    int done = 0;
    private int back(TreeNode cur) {
        if(cur.left==null && cur.right==null){
            if(cur==t1||cur==t2){
                return 1;
            }
            return 0;
        }


        int L = 0;
        if(cur.left!=null) {
            L = back(cur.left);
        }
        int R = 0;
        if(cur.right!=null) {
            R = back(cur.right);
        }

        if(done==0){
            if(((cur==t1||cur==t2) && L+R==1)
                            || (L+R==2)){
                zuxian = cur;
                done=1;
            }
        }
        return L+R + (cur==t1||cur==t2?1:0);
    }
}
